package edu.dayu.demo3;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 第一个字符串的排列之一是第二个字符串的 子串
 * 输入: s1 = "ab" s2 = "eidbaooo"
 * 输出: True
 * 解释: s2 包含 s1 的排列之一 ("ba").
 *
 * 思路：排列之一即可，那就是 s2 字串包含 s1 的字符即可。
 *      1、用数组存储，下标代表 字符，值代表个数，默认 0。  可以过，但效率很低。
 */
public class 字符串中的变位词 {
    public static void main(String[] args) {
        String s1 = "ab";
        String s2 = "eidbaooo";
        System.out.println(checkInclusion(s1,s2));
    }

    public static boolean checkInclusion(String s1, String s2) {
        int[] str = new int[26];
        for (int i = 0; i < s1.length(); i++) {
            str[s1.charAt(i)-'a']++;
        }
        int left = 0;
        int right = 0;
        while (left<=(s2.length()-s1.length())){
            int i = s2.charAt(left)-'a';
            int[] temp = Arrays.copyOf(str,str.length);
            while (temp[i]-->0){
                right++;
                if (right-left==s1.length())
                    return true;
                i = s2.charAt(right)-'a';
            }
            right = ++left;
        }
        return false;
    }

}
